package dstree

import (
	"container/heap"
	"encoding/json"
	"fmt"
)

type Query_result struct {
	Distance        Ts_type
	Node            *Dstree_Node
	Series          []Ts_type
	PQueue_position int
}

// 执行knn查询返回证明
func (index *Dstree_Index) exact_Knn_search_With_VO(query_ts []Ts_type, k int) ([]Query_result, VO) {
	//执行knn查询
	exact_result := index.exact_Knn_search(query_ts, k)
	//生成VO
	var vo VO
	vo.Values = make([]string, 0)
	nodeinfostring := index.Get_nodeinfo(index.firstNode)
	vo.Values = append(vo.Values, nodeinfostring)
	index.traverse_Exact_Knn_Search_VO(index.firstNode, query_ts, &exact_result[k-1], &vo)
	return exact_result, vo
}

func extract_knn_TS(results []Query_result) [][]Ts_type {

	kresults := make([][]Ts_type, 0)
	for _, result := range results {
		kresults = append(kresults, result.Series)
	}
	return kresults
}

func (index *Dstree_Index) extract_knn_result(results []Query_result, k int) ([]string, [][]Ts_type) {

	kobjID := make([]string, k)
	kresults := make([][]Ts_type, 0)
	i := 0
	for _, result := range results {
		if i == k {
			break
		}
		hash := tsdataToHash(result.Series)
		objid := index.objectIDmap[hash]
		//删除
		if index.isdeleted(objid) {
			continue
		} else {
			kobjID[i] = objid
			kresults = append(kresults, result.Series)
			i++
		}
	}
	return kobjID, kresults
}

// 现用knn近似搜索返回object id 和proof
func (index *Dstree_Index) Knn_search(query_ts []Ts_type, k int) ([]string, [][]float32, []byte) {
	knn_results, vo_result := index.exact_Knn_search_With_VO(query_ts, k+index.deletednum)

	kobjID, kresults := index.extract_knn_result(knn_results, k)
	proof := Dstree_Proof{
		ObjectID: kobjID,
		Data:     kresults,
		VO:       vo_result.Values,
	}
	proofjson, err := json.Marshal(proof)
	if err != nil {
		fmt.Printf("error")
	}
	return kobjID, kresults, proofjson
}

func (index *Dstree_Index) approximate_knn_search(query_ts []Ts_type, k int) ([]Query_result, VO) {
	knn_results := make(PqItemSeries, k)
	for i := 0; i < k; i++ {
		knn_results[i] = Query_result{Node: nil, Distance: MaxtsType}
	}
	var vo_result VO
	vo_result.Values = make([]string, 0)
	node := index.firstNode
	// fmt.Printf("search route:")
	if node != nil {
		//是内部节点，导航到叶子节点
		for !node.Is_leaf {
			self := Dstree_node_write_to_byte(node)
			vo_result.Values = append(vo_result.Values, string(self))
			if node.Node_split_policy_route_to_left(query_ts) {
				// fmt.Printf("left ")
				vo_result.Values = append(vo_result.Values, string(node.Right_child.Digest))
				node = node.Left_child
			} else {
				// fmt.Printf("right ")
				vo_result.Values = append(vo_result.Values, string(node.Left_child.Digest))
				node = node.Right_child
			}
		}
		// fmt.Printf("\n")
		Calculate_node_knn_distance(node, query_ts, k, knn_results)
		self := Dstree_node_write_to_byte(node)
		vo_result.Values = append(vo_result.Values, string(self))
		data := convertToBytes(*node.data)
		vo_result.Values = append(vo_result.Values, string(data))
	}
	return knn_results, vo_result
}

func (index *Dstree_Index) exact_Knn_search(query_ts []Ts_type, k int) []Query_result {
	exact_result, _ := index.approximate_knn_search(query_ts, k)
	approximate_result_node := exact_result[0].Node
	if len(exact_result) != k {
		return exact_result
	}
	kth_bsf_result := exact_result[k-1]

	pq := make(PqItemSeries, 0)
	heap.Init(&pq)
	heap.Push(&pq, kth_bsf_result)

	//Add the root to the priority queue
	root_result := Query_result{
		Node:     index.firstNode,
		Distance: Calculate_node_min_distance(index.firstNode, query_ts),
	}

	heap.Push(&pq, root_result)

	var n Query_result
	for pq.Len() > 0 {
		n = heap.Pop(&pq).(Query_result)
		if n.Distance > kth_bsf_result.Distance {
			// fmt.Printf("HEAP TOP %s's MIN distance %f LESS than bsf %f, BREAK \n", n.Node.Name, n.Distance, bsf_result.Distance)
			break
		}
		if n.Node.Is_leaf {
			if n.Node.Name == approximate_result_node.Name {
				continue
			}
			Calculate_node_knn_distance(n.Node, query_ts, k, exact_result)
			distance := exact_result[k-1].Distance

			//出现更精确距离，更新bsf
			if kth_bsf_result.Distance > distance {
				// fmt.Printf("%s's exact distance %f LESS than bsf, update bsf \n", n.Node.Name, distance)
				kth_bsf_result = exact_result[k-1]
			}
		} else {
			child_distance := Calculate_node_min_distance(n.Node.Left_child, query_ts)
			if child_distance < kth_bsf_result.Distance {
				mindist_result_left := Query_result{
					Node:     n.Node.Left_child,
					Distance: child_distance,
				}
				heap.Push(&pq, mindist_result_left)
				// fmt.Printf("%s's Leftchild %s min distance %f LESS than bsf , push it into heap\n", n.Node.Name, n.Node.Left_child.Name, child_distance)
			}

			child_distance = Calculate_node_min_distance(n.Node.Right_child, query_ts)
			if child_distance < kth_bsf_result.Distance {
				mindist_result_right := Query_result{
					Node:     n.Node.Right_child,
					Distance: child_distance,
				}
				heap.Push(&pq, mindist_result_right)
				// fmt.Printf("%s's Rightchild %s min distance %f LESS than bsf, push it into heap\n", n.Node.Name, n.Node.Right_child.Name, child_distance)
			}
		}
	}

	return exact_result
}

func (index *Dstree_Index) traverse_Exact_Knn_Search_VO(node *Dstree_Node, query_ts []Ts_type, kth_bsf_result *Query_result, vo *VO) error {
	// fmt.Printf("Traverse node %s\n", node.Name)
	if node.Is_leaf {
		databyte := convertToBytes(*node.data)
		vo.Values = append(vo.Values, string(databyte))
		return nil

	} else {
		//是否需要延左孩子继续遍历
		child_distance := Calculate_node_min_distance(node.Left_child, query_ts)
		vo.Values = append(vo.Values, index.Get_nodeinfo(node.Left_child))
		if child_distance < kth_bsf_result.Distance {
			err := index.traverse_Exact_Knn_Search_VO(node.Left_child, query_ts, kth_bsf_result, vo)
			if err != nil {
				return err
			}
		} else {
			//pruned node
			if node.Left_child.Is_leaf {
				//pruned leaf node
				// fmt.Printf("          pruned leaf node add %s data digetst\n", node.Left_child.Name)
				datadigest := Get_node_data_digest(node.Left_child)
				vo.Values = append(vo.Values, datadigest)
			} else {
				//pruned internal node
				// fmt.Printf("          pruned internal node add %s l&r childs digetst\n", node.Left_child.Name)
				vo.Values = append(vo.Values, string(node.Left_child.Left_child.Digest))
				vo.Values = append(vo.Values, string(node.Left_child.Right_child.Digest))
			}

		}

		//是否需要延右孩子继续遍历
		child_distance = Calculate_node_min_distance(node.Right_child, query_ts)
		vo.Values = append(vo.Values, index.Get_nodeinfo(node.Right_child))
		if child_distance < kth_bsf_result.Distance {
			err := index.traverse_Exact_Knn_Search_VO(node.Right_child, query_ts, kth_bsf_result, vo)
			if err != nil {
				return err
			}
		} else {
			//pruned internal node
			if node.Right_child.Is_leaf {
				// fmt.Printf("          pruned leaf node add %s data digetst\n", node.Right_child.Name)
				datadigest := Get_node_data_digest(node.Right_child)
				vo.Values = append(vo.Values, datadigest)
			} else {
				// fmt.Printf("          pruned internal node add %s l&r childs digetst\n", node.Right_child.Name)
				vo.Values = append(vo.Values, string(node.Right_child.Left_child.Digest))
				vo.Values = append(vo.Values, string(node.Right_child.Right_child.Digest))
			}
		}
	}
	return nil
}
